package 二叉树相关问题.BST;

import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class 二叉搜索树序列 {
    public List<List<Integer>> BSTSequences(TreeNode root) {
        if (root == null) {
            List<List<Integer>> r = new ArrayList<>();
            r.add(new ArrayList<>());
            return r;
        }
        List<List<Integer>> lefts = BSTSequences(root.left);
        List<List<Integer>> rights = BSTSequences(root.right);
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> collector = new LinkedList<>();
        collector.add(root.val);
        for (List<Integer> left : lefts) {
            for (List<Integer> right : rights) {
                backtrack(left, 0, right, 0, collector, res);
            }
        }
        return res;
    }

    private void backtrack(List<Integer> left, int l, List<Integer> right, int r,
                           LinkedList<Integer> collector, List<List<Integer>> result) {
        //结束条件为啥是这个，没搞懂
        if (l >= left.size() && r >= right.size()) {
            result.add(new ArrayList<>(collector));
            return;
        }
        if (l < left.size()) {
            collector.addLast(left.get(l));
            backtrack(left, l + 1, right, r, collector, result);
            collector.removeLast();
        }
        if (r < right.size()) {
            collector.addLast(right.get(r));
            backtrack(left, l, right, r + 1, collector, result);
            collector.removeLast();
        }
    }
    @Test
    public void test(){
        TreeNode root=new TreeNode(2);
        root.left=new TreeNode(1);
        root.right=new TreeNode(3);
        System.out.println(BSTSequences(root));
        List<List<Integer>> lists = BSTSequences(root);
        for (List<Integer> list : lists) {
            System.out.println(list.toString());
        }
    }
}
